/* 

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

 

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：

输入：nums = [0]
输出：[0]
示例 4：

输入：nums = [1]
输出：[1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

// 单指针
var sortColors = function (nums) {
    const n = nums.length;
    let p0 = 0;

    for (let i = p0; i < n; i++) {
        if (nums[i] === 0) {
            [nums[p0],nums[i]] = [nums[i], nums[p0]];
            p0++;
        }
    }

    let p1 = p0;

    for (let i = p1; i < n; i++) {
        if (nums[i] === 1) {
            [nums[p1],nums[i]] = [nums[i], nums[p1]];
            p1++;
        }
    }
};

// 单指针
var sortColors = function (nums) {
    const n = nums.length;
    let p0 = p1 = 0;

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) {
            [nums[p0],nums[i]] = [nums[i], nums[p0]];
            if (p0 < p1) {
                // 上一步的置换把p1颜色放到了i处，此时应该再次置换使得这个p1颜色放回p1位置上
                [nums[p1],nums[i]] = [nums[i], nums[p1]];
            }
            p0++;
            p1++;
        } else if (nums[i] === 1) {
            [nums[p1],nums[i]] = [nums[i], nums[p1]];
            p1++;
        }
    }

    return nums;
};